#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

//HJ1 字符串最后一个单词的长度
//https://www.nowcoder.com/practice/8c949ea5f36f422594b306a2300315da?tpId=37&&tqId=21224&rp=5&ru=/activity/oj&qru=/ta/huawei/question-ranking

/*
void test1(){
    string s1;
    getline(cin,s1);
    size_t pos = s1.rfind(' ');
    string s2(s1,pos+1);
    cout << s2.size() << endl;
}

void test2(){
    string s1;
    getline(cin,s1);
    size_t pos = s1.rfind(' ');
    int num = 0;
    for (size_t i = pos+1; i < s1.size(); ++i) {
        ++num;
    }
    cout << num << endl;
}

void test3(){
    string s1;
    getline(cin,s1);
    size_t pos = s1.rfind(' ');
    if (pos != string::npos){
        cout << s1.size() - pos - 1 << endl;
    } else
        cout << s1.size() << endl;
}

int main() {
    test3();
    return 0;
}
*/

//415. 字符串相加
//https://leetcode.cn/problems/add-strings/

/*
class Solution {
public:
    string addStrings(string num1, string num2) {
        int end1 = num1.size() - 1, end2 = num2.size() - 1;
        string ret;
        int val1 = 0, val2 = 0, next = 0;
        while (end1 >= 0 || end2 >= 0){
            val1 = end1 >= 0 ? num1[end1--] - '0' : 0;
            val2 = end2 >= 0 ? num2[end2--] - '0' : 0;
            int val = val1 + val2 + next;
            next = val / 10;
            val %= 10;
            ret.insert(0,1,val+'0');
        }
        if (next == 1)
            ret.insert(0,1,'1');
        return ret;
    }
};
*/

//优化：提前扩容到位 + 避免头插，改为先尾插再翻转
/*
class Solution {
public:
    string addStrings(string num1, string num2) {
        int end1 = num1.size() - 1, end2 = num2.size() - 1;
        string ret;
        ret.reserve(num1.size() > num2.size() ? num1.size()+1 : num2.size()+1);
        int val1 = 0, val2 = 0, next = 0;
        while (end1 >= 0 || end2 >= 0){
            val1 = end1 >= 0 ? num1[end1--] - '0' : 0;
            val2 = end2 >= 0 ? num2[end2--] - '0' : 0;
            int val = val1 + val2 + next;
            next = val / 10;
            val %= 10;
            ret += (val + '0');
        }
        if (next == 1)
            ret += '1';
        reverse(ret.begin(),ret.end());
        return ret;
    }
};
*/

/*
int main(int argc, char *argv[])
{
    string a="hello world";
    string b=a;
    if (a.c_str()==b.c_str())
    {
        cout<<"true"<<endl;
    }
    else cout<<"false"<<endl;
    string c=b;
    c="";
    if (a.c_str()==b.c_str())
    {
        cout<<"true"<<endl;
    }
    else cout<<"false"<<endl;
    a="";
    if (a.c_str()==b.c_str())
    {
        cout<<"true"<<endl;
    }
    else cout<<"false"<<endl;
    return 0;
}
*/

/*
int main(){
    string str("Hello Bit.");
    str.reserve(111);
    str.resize(5);
    str.reserve(50);
    cout<<str.size()<<":"<<str.capacity()<<endl;
    return 0;
}
*/

//把字符串转换成整数
//https://www.nowcoder.com/practice/1277c681251b4372bdef344468e4f26e?tpId=13&&tqId=11202&rp=6&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking

/*
class Solution{
public:
    static int StrToInt(string str){
        int index = 0, flag = 1;
        long long ret = 0;
        while (str[index] == ' ')
            ++index;
        if (str[index] == '-' || str[index] == '+'){
            if (str[index] == '-')
                flag = -1;
            ++index;
        }
        while (index < str.size() && isdigit(str[index])){
            ret = ret * 10 + (str[index] - '0');
            if (ret >= INT_MAX && flag == 1)
                return INT_MAX;
            if (ret <= INT_MIN && flag == -1)
                return INT_MIN;
            ++index;
        }
        if (index == str.size())
            return flag * ret;
        else
            return 0;
    }
};
*/

//344. 反转字符串
//https://leetcode.cn/problems/reverse-string/

/*
class Solution {
public:
    static void reverseString(vector<char>& s) {
        auto left = s.begin(), right = s.end() - 1;
        while (left < right){
*/
/*            char tmp = *left;
            *left = *right;
            *right = tmp;*//*

            swap(*left,*right);
            ++left, --right;
        }
    }
};
*/

/*
class Solution {
public:
    void reverseString(vector<char>& s) {
        int n = s.size();
        for (int left = 0, right = n - 1; left < right; ++left, --right) {
            swap(s[left], s[right]);
        }
    }
};
*/

/*
class Solution {
public:
    void reverseString(vector<char>& s) {
        reverse(s.begin(), s.end());
    }
};
*/

/*
void test(){
    char str[] = {'h','e','l','l','o'};
    vector<char> c1(str,str + sizeof(str)/ sizeof(char));
    for (auto pc:c1) {
        cout << pc;
    }
    cout << endl;
    Solution::reverseString(c1);
    for (auto pc:c1) {
        cout << pc;
    }
}

int main(){
    test();
    return 0;
}
*/

//387. 字符串中的第一个唯一字符
//https://leetcode.cn/problems/first-unique-character-in-a-string/

/*
class Solution {
public:
    static int firstUniqChar(string s){
        for(int i=0; i<s.size(); ++i){
            int index = s.find(s[i]);
            int reverse_index = s.rfind(s[i]);
            if(index == reverse_index)
                return i;
        }
        return -1;
    }
};
*/

//125. 验证回文串
//https://leetcode.cn/problems/valid-palindrome/

/*
class Solution {
public:
    static string newString(const string& s){
        string alphanumString;
        alphanumString.reserve(s.size());
        for (char i : s) {
            if (isalnum(i))
                alphanumString.push_back(i);
        }
        return alphanumString;
    }
    static bool isPalindrome(const string& s) {
        string s1 = newString(s);
        if (s1.empty())
            return true;
        for (char & i : s1) {
            if (i >= 'A' && i <= 'Z')
                i += 32;
        }
        const char *begin = s1.c_str();
        const char *end = s1.c_str() + s1.size() - 1;
        while (begin < end){
            if (*begin != *end)
                return false;
            ++begin;
            --end;
        }
        return true;
    }
};

int main(){
    string s1 = "A man, a plan, a canal: Panama";
    cout << s1 << endl;
    cout << Solution::newString(s1) << endl;
    cout << Solution::isPalindrome(s1) << endl;
    string s2 = "hello89 _";
    cout << Solution::isPalindrome(s2) << endl;
    string s3 = "";
    cout << Solution::isPalindrome(s3) << endl;
    return 0;
}
*/

/*
class Solution {
public:
    static bool isPalindrome(string s) {
        int left = 0, right = s.size() - 1;
        while (left < right) {
            while (left < right && !isalnum(s[left])) {
                ++left;
            }
            while (left < right && !isalnum(s[right])) {
                --right;
            }
            if (left < right) {
                if (tolower(s[left]) != tolower(s[right])) {
                    return false;
                }
                ++left;
                --right;
            }
        }
        return true;
    }
};
*/


//541. 反转字符串 II
//https://leetcode.cn/problems/reverse-string-ii/

/*
class Solution {
public:
    static string reverseStr(string s, int k) {
        int n = s.length();
        for (int i = 0; i < n; i += 2 * k) {
            reverse(s.begin() + i, s.begin() + min(i + k, n));
        }
        return s;
    }
};
*/

//557. 反转字符串中的单词 III
//https://leetcode.cn/problems/reverse-words-in-a-string-iii/

/*
class Solution {
public:
    static string reverseWords(string s) {
        size_t pos = s.find(' ');
        if (pos == string::npos){
            reverse(s.begin(), s.end());
            return s;
        }
        string::iterator begin = s.begin();
        string::iterator end = s.begin() + pos;
        while (pos != string::npos){
            reverse(begin,end);
            begin = s.begin() + pos + 1;
            pos = s.find(' ',pos + 1);
            end = s.begin() + pos;
        }
        pos = s.rfind(' ');
        reverse(s.begin() + pos + 1,s.end());
        return s;
    }
};

int main(){
    string s = "Let's take LeetCode contest";
    cout << s << endl;
    cout << Solution::reverseWords(s) << endl;
    string s1 = "hello";
    cout << s1 << endl;
    cout << Solution::reverseWords(s1) << endl;
    return 0;
}
*/

/*class Solution{
public:
    static string reverseWords(string s){
        string ret;
        ret.reserve(s.size());
        int i = 0;
        while (i < s.size()){
            int start = i;
            while (i < s.size() && s[i] != ' ')
                ++i;
            for (int j = start; j < i; ++j) {
                ret.push_back(s[i + start - j - 1]);
            }
            while (i < s.size() && s[i] == ' '){
                ++i;
                ret.push_back(' ');
            }
        }
        return ret;
    }
};*/

/*
class Solution{
public:
    static string reverseWords(string s){
        string ret;
        ret.reserve(s.size());
        int i = 0;
        while (i < s.size()) {
            int start = i;
            while (i < s.size() && s[i] != ' ')
                ++i;
            int left = start, right = i - 1;
            while (left < right){
                swap(s[left], s[right]);
                ++left;
                --right;
            }
            while (i < s.size() && s[i] == ' ')
                ++i;
        }
        return s;
    }
};
*/

//43. 字符串相乘
//https://leetcode.cn/problems/multiply-strings/

/*
class Solution {
public:
    static string addStrings(string num1, string num2) {
        int end1 = num1.size() - 1, end2 = num2.size() - 1;
        string ret;
        ret.reserve(num1.size() > num2.size() ? num1.size()+1 : num2.size()+1);
        int val1 = 0, val2 = 0, next = 0;
        while (end1 >= 0 || end2 >= 0){
            val1 = end1 >= 0 ? num1[end1--] - '0' : 0;
            val2 = end2 >= 0 ? num2[end2--] - '0' : 0;
            int val = val1 + val2 + next;
            next = val / 10;
            val %= 10;
            ret += (val + '0');
        }
        if (next == 1)
            ret += '1';
        reverse(ret.begin(),ret.end());
        return ret;
    }
    static string multiply(string num1, string num2) {
        if (num1 == "0" || num2 == "0")
            return "0";
        string ret = "0";
        ret.reserve(num1.size() + num2.size());
        int m = num1.size(), n = num2.size();
        for (int i = n - 1; i >= 0; --i) {
            string cur;
            cur.reserve(num1.size() + 1);
            int add = 0;
            //高位补0
            for (int j = n - 1; j > i; --j) {
                cur.push_back(0);
            }
            int y = num2[i] - '0';
            //第二个数的i位依次与第一个数的每一位相乘
            for (int j = m - 1; j >= 0; --j) {
                int x = num1[j] - '0';
                int product = x * y + add;
                cur.push_back(product % 10);
                add = product / 10;
            }
            //处理最后的进位
            while (add != 0){
                cur.push_back(add % 10);
                add /= 10;
            }
            //因为是尾插所以逆序
            reverse(cur.begin(),cur.end());
            //数字转字符
            for (auto & j : cur) {
                j += '0';
            }
            //将每次相乘的结果相加
            ret = addStrings(ret,cur);
        }
        return ret;
    }
};

int main(){
    string num1 = "111", num2 = "10";
    cout << Solution::multiply(num1, num2);
    return 0;
}
*/

/*
class Solution {
public:
    static string multiply(string num1, string num2) {
        if (num1 == "0" || num2 == "0")
            return "0";
        int m = num1.size(), n = num2.size();
        auto ansArr = vector<int>(m + n);
        for (int i = m - 1; i >= 0; i--) {
            int x = num1.at(i) - '0';
            for (int j = n - 1; j >= 0; j--) {
                int y = num2.at(j) - '0';
                ansArr[i + j + 1] += x * y;
            }
        }
        for (int i = m + n - 1; i > 0; i--) {
            ansArr[i - 1] += ansArr[i] / 10;
            ansArr[i] %= 10;
        }
        int index = ansArr[0] == 0 ? 1 : 0;
        string ret;
        ret.reserve(m + n);
        while (index < m + n) {
            ret.push_back(ansArr[index]);
            index++;
        }
        for (auto &c: ret) {
            c += '0';
        }
        return ret;
    }
};

int main(){
    string num1 = "123", num2 = "567";
    cout << Solution::multiply(num1, num2);
    return 0;
}
*/
